package LimitedTimeGame.Day_0226;

/**
 * @author zxc
 * @date 2023/02/26 09:32
 **/
/**
 * 题目 ：得分最高的单词集合
 * 题目详述 ：
 * 你将会得到一份单词表words，一个字母表letters（可能会有重复字母），以及每个字母对应的得分情况表score。
 * 请你帮忙计算玩家在单词拼写游戏中所能获得的「最高得分」：能够由letters里的字母拼写出的任意属于 words单词子集中，分数最高的单词集合的得分。
 * 单词拼写游戏的规则概述如下：
 * 玩家需要用字母表letters 里的字母来拼写单词表words中的单词。
 * 可以只使用字母表letters 中的部分字母，但是每个字母最多被使用一次。
 * 单词表 words中每个单词只能计分（使用）一次。
 * 根据字母得分情况表score，字母 'a','b','c', ... ,'z' 对应的得分分别为 score[0], score[1],...,score[25]。
 * 本场游戏的「得分」是指：玩家所拼写出的单词集合里包含的所有字母的得分之和
 *
 * 提示：
 *
 * 1 <= words.length <= 14
 * 1 <= words[i].length <= 15
 * 1 <= letters.length <= 100
 * letters[i].length == 1
 * score.length ==26
 * 0 <= score[i] <= 10
 * words[i]和letters[i]只包含小写的英文字母。
 *
 */
public class MaxScoreWords02 {
    /**
     * 思路 ：
     * ===》
     * 回溯法，来获取所有可能的情况 && 同时，从所有可能情况中获取最优解（得分最高的单词集合）;
     * 核心 ：回溯结束条件 + 递归恢复机制;
     *
     * @param words
     * @param letters
     * @param score
     * @return
     */
    public int maxScoreWords(String[] words, char[] letters, int[] score) {
        int[] dp = new int[26];
        // 统计letters数组中，所有letter可能出现的情况;
        for (char letter : letters) {
            dp[letter - 'a']++;
        }
        // 从words数组的第 len个元素开始遍历，直至第1个元素;
        int len = words.length - 1;
        //
        return dfs(words , score , dp , len);
    }
    // dfs方法的返回值 ：选择/不选择第len个元素，所能够得到的最高分数;
    private int dfs(String[] words, int[] score, int[] dp , int len) {
        // 递归结束条件 ：words数组中所有元素都已经被遍历
        if(len < 0){
            return 0;
        }

        // （1）不选择当前元素
        int NoChooseRes = dfs(words , score , dp , len - 1);

        // （2）选择当前元素
        // ===》（需要 对其进行判断，是否能够在letters数组中寻找到该单词;）
        // 由于回溯需要对于temp数组中进行恢复，所以所传递的应该是 dp.clone();
        int[] temp = dp.clone();
        int value = 0;
        for (char ch : words[len].toCharArray()) {
            // 若是letters数组中，某个字符的数量 == 0的话，那么代表该单词不能够加入;
            if(temp[ch - 'a'] == 0) {
                // 若是当前单词不能够选择，那么只有不选择当前单词一种情况;
                return NoChooseRes;
            }
            temp[ch - 'a']--;
            value += score[ch - 'a'];
        }
        return Math.max(NoChooseRes , value + dfs(words , score , temp , len - 1));
    }
}
